package com.ryujung.dfs_backtracking;

import java.util.*;

class Solution17 {

    /**
     * 使用hash映射关系
     * 解答成功:
     * 执行耗时:0 ms,击败了100.00% 的Java用户
     * 内存消耗:39.8 MB,击败了92.22% 的Java用户
     */
    public List<String> letterCombinations(String digits) {
        HashMap<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        List<String> res = new ArrayList<>();
        if (digits == null || digits.isEmpty()) {
            return res;
        }
        dfs(digits, map, 0, new StringBuilder(), res);
        return res;
    }

    private void dfs(String digits, Map<Character, String> keyMap, int curDigitsIndex,
                     StringBuilder sb, List<String> res) {
        if (sb.length() == digits.length()) {
            res.add(sb.toString());
            return;
        }
        String keyMapStr = keyMap.get(digits.charAt(curDigitsIndex));
        //
        for (int i = 0; i < keyMapStr.length(); i++) {
            sb.append(keyMapStr.charAt(i));
            dfs(digits, keyMap, curDigitsIndex + 1, sb, res);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    /**
     * 使用数组映射关系
     * <p>
     * 解答成功:
     * 执行耗时:0 ms,击败了100.00% 的Java用户
     * 内存消耗:40 MB,击败了62.65% 的Java用户
     */
    public List<String> letterCombinations1(String digits) {
        String[] digitMapArr = new String[]{"", "",
                "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return res;
        }
        int digitsNum = Integer.parseInt(digits);
        dfs1(digitsNum, digitMapArr, digits.length(), res, new StringBuilder());
        return res;
    }

    private void dfs1(Integer digitsNum, String[] digitMapArr, int len, List<String> res, StringBuilder sb) {
        if (digitsNum % 10 == 0) {
            if (sb.length() == len) {
                res.add(sb.toString());
            }
            return;
        }
        int curDigit = digitsNum % 10;
        String str = digitMapArr[curDigit];
        for (int i = 0; i < str.length(); i++) {
            sb.insert(0, str.charAt(i));
            dfs1(digitsNum / 10, digitMapArr, len, res, sb);
            sb.delete(0, 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(Integer.valueOf("1234".substring(0, 1)));

        Solution17 s = new Solution17();
        System.out.println(s.letterCombinations("23"));
    }
}